package lc.q101_150;

import lc.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Q109 {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> arrs = new ArrayList<>();
        while (head != null){
            arrs.add(head.val);
            head = head.next;
        }
        return sortedListToBST(arrs);
    }

    private TreeNode sortedListToBST(List<Integer> nodes) {
        if (nodes.size() == 0) {
            return null;
        }
        int mid = nodes.size() / 2;
        final TreeNode root = new TreeNode(nodes.get(mid));
        root.left = sortedListToBST(nodes.subList(0, mid));
        root.right = sortedListToBST(nodes.subList(mid + 1, nodes.size()));
        return root;
    }
}
